\documentclass{beamer}




\mode<presentation>
{
  \usetheme{Warsaw}
  % or ...

  \setbeamercovered{transparent}
  % or whatever (possibly just delete it)
}


\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{graphicx}


\title
{A Survey of the Game ``Lights Out''}



\author
{Jiajin Yu}

\date
{Advisor: Prof. Rudolf Fleischer}


\subject{Theoretical Computer Science}


% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
% \logo{\pgfuseimage{university-logo}}



% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}


\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}


% Structuring a talk is a difficult task and the following structure
% may not be suitable. Here are some rules that apply for this
% solution: 

% - Exactly two or three sections (other than the summary).
% - At *most* three subsections per section.
% - Talk about 30s to 2min per frame. So there should be between about
%   15 and 30 frames, all told.

% - A conference audience is likely to know very little of what you
%   are going to talk about. So *simplify*!
% - In a 20min talk, getting the main ideas across is hard
%   enough. Leave out details, even if it means being less precise than
%   you think necessary.
% - If you omit details that are vital to the proof/implementation,
%   just say so once. Everybody will be happy with that.

\section{Introduction}
\begin{frame}
  \frametitle{What is ``Lights Out!''?}
  \begin{itemize}
  \item
    A single-person combinatorial game
  \item
    Also called $\sigma^+$-game \cite{Sut89}
  \item
    $n\times n$ chess board where each cell has a light.
  \item 
    Pushing a cell flips the states of its rectilinear neighbors and itself.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{A Simple Example}
   \includegraphics[scale=0.6]<1->{l1}\hspace{1cm}
   \includegraphics[scale=0.6]<2->{l2}\hspace{1cm}
   \includegraphics[scale=0.6]<3->{l3}
\end{frame}


\begin{frame}
  \frametitle{Formal Definition}
  \begin{itemize}
  \item Given $G=(V,E)$\pause
  \item Each vertex $v$ has a state $c_v \in \{0,1\}$\pause
  \item Assign a state to each vertex initially\pause
  \item Selecting a vertex changes the state of its neighbors and itself\pause
  \item Selecting several vertices forms an \alert{activation set} $X\subseteq V$ to
    switch off all vertices.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Previous Studies}
\end{frame}



\section{All \texttt{ON} to All \texttt{OFF} Is Always Realizable}
\begin{frame}
  \frametitle{A Graph Theoretic Proof}
  \begin{itemize}
  \item Induction proof based on the number of vertices of $G$
  \item Argument the parity domination for each vertex 
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{A Linear Algebra Proof}
  \begin{itemize}
  \item Adjacent matrix $A$ whose diagonal is all 1
  \item Vector $x$ is the characteristic vector of the activation set $X$
  \item ``$Ax=1$ is always solvable'' is equivalent to ``All on to all off is
    always realizable''
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{$Ax = 1$}
  \begin{itemize}
  \item Each vertex is from $c_v = 1$ to $c_v =0$\pause
  \item $c_v + \sum_{x_w \in N[v]}x_w = c'_v$\pause
  \item One row in $Ax=1$ is $\sum_{x_w \in N[v]}x_w = c'_v -c_v = 1$
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Why $Ax=1$ is always solvable}
  \begin{itemize}
  \item Try to prove ``1 is in the column space of adjacent matrix $A$''\pause
  \item Try to prove ``1 is orthogonal to the vectors in the kernel of $A$''\pause
  \item First prove that every vector in the kernel has an even number of 1's.\pause
  \item Then $1\cdot x^T = 0$, for all $x\in \ker(A)$.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{A $3\times 3$ example}
\end{frame}

\section{Completely Solvable}

\subsection{Grid Graphs}

\begin{frame}
  \frametitle{Grid Graphs}
  \begin{itemize}
  \item
    An $m\times n$ grid has $m\times n$ vertices.\pause
  \item
    A vertex $v$ denoted by $(i,j)$ in row $i$ and column $j$ is connected to
    vertices $(i-1, j), (i+1, j), (i, j-1), (i, j+1)$.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Analysis of the kernel of adjacent matrix $A$}
  \begin{itemize}
  \item $c_v + \sum_{x_w \in N[v]}x_w = c'_v$\pause
  \item $c'_v = 0$, $\sum_{x_w \in N[v]}x_w = c_v$\pause
  \item For the whole graph, we have $Ax = y, y \in \mathbb{F}_2^n$\pause
  \item All initial configurations are solvable, then each element in $\mathbb{F}_2^n$
    becomes one $y$.\pause
  \item The dimension of column space is $n$, then the nullity of $A$ is 0.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{$\sigma$-game}
  \begin{itemize}
  \item Simpler rules, only neighbors change their states.
  \item \alert{Fibonacci polynomials}: $f_{i+1}(x) = xf_i(x) + f_{i-1}(x)$
  \item $B_m$ is a $m\times m$ submatrix of the adjacent matrix $A$
  \item The dimension of $\ker(A)$ are the same as $f_n(B_m)$ and $f_m(B_n)$
  \item Use some properties of Fibonacci polynomials to analyze the kernel of $f_n(B_m)$.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{$\sigma^+$-game}
  \begin{itemize}
  \item Adjacent matrix $A$ is different, therefore $B_m$ is different
  \item The difference cause that $\dim(\ker(A)) = \dim(\ker(f_n(B_m))) =
    \dim(\ker(f_m(B_n + I)))$
  \item Difficult to analyze the kernel and characterization. 
  \end{itemize}
\end{frame}

\subsection{Several Other Graph Classes}
\begin{frame}
  \frametitle{Some Graph Classes}
  \begin{itemize}
  \item Path \pause
  \item Spider, Caterpillar \pause
  \item Tree
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Parity Domination Set}
  \begin{itemize}
  \item \alert{Parity domination set} $X$ is a subset of $V$.
  \item Vertex $v$ is \alert{odd} covered if there are odd vertices in $X$ has
    connections to $v$.
  \item Activation set $X$ to turn off all vertices is a parity domination set.
  \item $Ax=0$ only has solution 0 means that the all-even parity set can only
    be $\emptyset$.
  \end{itemize}
\end{frame}

\section{Optimize Problems}
\begin{frame}
  \frametitle{ddd}
\end{frame}

% All of the following is optional and typically not needed. 
\appendix
\section{References}
\begin{frame}[allowframebreaks]
  \frametitle<presentation>{References}
  \bibliographystyle{abbrv}
  \bibliography{paper}
\end{frame}

\end{document}


